typedef unsigned long long ULL;
typedef long long LL;

LL Base1 = 29;
LL Base2 = 131;
LL MOD1 = 1e9 + 7;
LL MOD2 = 1e9 + 9;
const LL MAXN = 3e6 + 10;
string s1;

string s2;
//高效比较两个字符串的子串是否相等
LL h11[MAXN],h12[MAXN],p1[MAXN],p2[MAXN];
LL h21[MAXN],h22[MAXN];

void distinctEchoSubstrings() 
{
    p1[0] = 1, p2[0] = 1;
    for(int i = 1;i < s1.size();i++)
    {
        h11[i] = (h11[i - 1]*Base1 + (s1[i] - 'a' + 1)) % MOD1;
        h12[i] = (h12[i - 1]*Base2 + (s1[i] - 'a' + 1)) % MOD2;
    }
    for(int i = 1;i < s2.size();i++)
    {
        h21[i] = (h21[i - 1]*Base1 + (s2[i] - 'a' + 1)) % MOD1;
        h22[i] = (h22[i - 1]*Base2 + (s2[i] - 'a' + 1)) % MOD2;
    }
    for(int i = 1;i <= max(s1.size(),s2.size());i++)
    {
        p1[i] = (p1[i-1]*Base1) % MOD1;
        p2[i] = (p2[i-1]*Base2) % MOD2;
    }
}
//双哈希
int gethash11(LL l, LL r)
{
    LL now_has11 = ((h11[r] - h11[l - 1] * p1[r - l + 1] % MOD1) + MOD1) % MOD1;
    return now_has11;
}
int gethash12(LL l, LL r)
{
    LL now_has12 = ((h12[r] - h12[l - 1] * p2[r - l + 1] % MOD2) + MOD2) % MOD2;
    return now_has12;
}
int gethash21(LL l, LL r)
{
    LL now_has21 = ((h21[r] - h21[l - 1] * p1[r - l + 1] % MOD1) + MOD1) % MOD1;
    return now_has21;
}
int gethash22(LL l, LL r)
{
    LL now_has22 = ((h22[r] - h22[l - 1] * p2[r - l + 1] % MOD2) + MOD2) % MOD2;
    return now_has22;
}
 



//自然溢出哈希
ULL Base = 29;
const ULL MAXN = 1e6 + 10;
string s1;
ULL p1[MAXN],h11[MAXN];

void hash1(string s)
{
    p1[0] = 1;
    ULL len=s.size();
    for(int i = 1;i < s.size();i++)
        h11[i] = (h11[i - 1]*Base + (s[i] - 'a' + 1));

    for(int i = 1;i < ls.size();i++)
    {
        p1[i] = (p1[i-1]*Base);
    }
}
ULL gethash11(LL l, LL r)
{
    ULL now_has11 = (h11[r] - h11[l - 1] * p1[r - l + 1]);
    return now_has11;
}